package find;

import org.junit.Test;

public class find {
    @Test
    public void test1() {
        //二分查找 (基于有序数组)
        int[] list = new int[]{1, 3, 5, 9, 10, 50, 52, 61};
        int find = 5;
        int start = 0;
        int end = list.length - 1;
        while (start <= end) {
            int idx = (start + end) / 2;
            if (list[idx] == find) {
                System.out.println(String.format("%d在数组下标%d处", find, idx));
                break;
            } else if (list[idx] > find) {
                end = idx - 1;
            } else {
                start = idx + 1;
            }
        }
    }

    @Test
    public void test2() {
        //二分查找 (基于有序数组)   查找最第一个值等于给定值的元素
        int[] list = new int[]{1, 3, 5, 5, 10, 11, 52, 53};
        int find = 5;
        int start = 0;
        int end = list.length - 1;
        while (start <= end) {
            int idx = (start + end) / 2;
            if (list[idx] == find) {//下标为0或者前一个数据不是要找的数据，那本数据就是第一个
                if (idx == 0 || list[idx - 1] != find) {
                    System.out.println(String.format("%d在数组下标%d处", find, idx));
                    break;
                }
                end = idx - 1;
            } else if (list[idx] > find) {
                end = idx - 1;
            } else {
                start = idx + 1;
            }
        }
    }

    @Test
    public void test3() {
        //二分查找 (基于有序数组)   查找最后一个值等于给定值的元素
        int[] list = new int[]{1, 3, 5, 5, 10, 11, 52, 53};
        int find = 5;
        int start = 0;
        int end = list.length - 1;
        while (start <= end) {
            int idx = (start + end) / 2;
            if (list[idx] > find) {
                end = idx - 1;
            } else if (list[idx] < find) {
                start = idx + 1;
            } else {//下标为查找区域末尾 或者后一个数据不是要找的数据，那本数据就是最后一个
                if (idx == end || list[idx + 1] != find) {
                    System.out.println(String.format("%d在数组下标%d处", find, idx));
                    break;
                }
                start = idx + 1;
            }
        }
    }

    @Test
    public void test4() {
        //二分查找 (基于有序数组)   查找第一个大于等于给定值的元素
        int[] list = new int[]{1, 3, 5, 5, 10, 10, 10, 10, 11, 52, 53};
        int find = 10;
        int start = 0;
        int end = list.length - 1;
        while (start <= end) {
            int idx = (start + end) / 2;
            if (list[idx] <= find) {
                start = idx + 1;
            } else {//下标为查找区域末尾 或者后一个数据不是要找的数据，那本数据就是最后一个
                if (list[idx - 1] <= find) {
                    System.out.println(String.format("第一个大于%d的元素是%d   下标:%d", find, list[idx], idx));
                    break;
                }
                end = idx - 1;
            }
        }
    }

    @Test
    public void test5() {
        //二分查找 (基于有序数组)   查找最后一个小于等于给定值的元素
        int[] list = new int[]{1, 3, 5, 5, 10, 10, 10, 10, 11, 52, 53};
        int find = 10;
        int start = 0;
        int end = list.length - 1;
        while (start <= end) {
            int idx = (start + end) / 2;
            if (list[idx] >= find) {
                end = idx - 1;
            } else {//下标为查找区域末尾 或者后一个数据不是要找的数据，那本数据就是最后一个
                if (list[idx + 1] >= find) {
                    System.out.println(String.format("最后一个小于%d的元素是%d  下标:%d", find, list[idx], idx));
                    break;
                }
                start = idx + 1;
            }
        }
    }
}
